import java.util.ArrayList;
import java.util.List;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
         this.val = val;
         this.left = left;
         this.right = right;
     }
}

class Solution {
    //计算布尔二叉树的值
    public boolean evaluateTree(TreeNode root) {
        //递归出口
        if(root.val == 0) return false;
        if(root.val == 1) return true;

        //
        if(root.val == 2){
            return evaluateTree(root.left) | evaluateTree(root.right);
        }else{
            return evaluateTree(root.right) & evaluateTree(root.left);
        }
    }
    //求根节点到叶节点数字之和
    public int sumNumbers(TreeNode root) {
        return sumNums(root, 0);
    }
    public int sumNums(TreeNode root, int prevSum){
        prevSum = prevSum * 10 + root.val;
        if(root.left == null && root.right == null) return prevSum;

        int ret = 0;
        if(root.left != null) ret += sumNums(root.left, prevSum);
        if(root.right != null) ret += sumNums(root.right, prevSum);

        return ret;
    }
    //二叉树剪枝
    public TreeNode pruneTree(TreeNode root) {
        //递归出口
        if(root == null) return root;

        root.left = pruneTree(root.left);
        root.right = pruneTree(root.right);

        if(root.left == null && root.right == null && root.val == 0) {
            root = null;
        }

        return root;
    }
    //二叉树剪枝
    private long prev = Long.MIN_VALUE;
    public boolean isValidBST(TreeNode root) {
        //递归出口
        if(root == null) {
            return true;
        }
        //剪枝
        if(!isValidBST(root.left)) return false;
        if(root.val <= prev){
            return false;
        }
        prev = root.val;
        return isValidBST(root.right);
    }
    //二叉搜索树中的第k小的元素
    private int count;
    private int ret;
    public int kthSmallest(TreeNode root, int k) {
        count = k;
        kthSmall(root);
        return ret;
    }
    public void kthSmall(TreeNode root){
        //递归出口
        if(root == null || count == 0) return;

        kthSmall(root.left);

        count--;
        if(count == 0) ret = root.val;
        if(count == 0) return;

        kthSmall(root.right);
    }

    //二叉树的所有路径
    private List<String> list = new ArrayList<>();
    public List<String> binaryTreePaths(TreeNode root) {
        dfs(root, "");
        return list;
    }
    public void dfs(TreeNode root, String path){

        path += Integer.toString(root.val);

        //递归出口
        if(root.left == null && root.right == null){
            list.add(path);
            return;
        }
        path += "->";
        if(root.left != null) dfs(root.left, path);
        if(root.right != null) dfs(root.right, path);
    }
}